package main.java;

/**
 * @program: pratice
 * @author: 关键我是大怪
 * @create: 2021-07-20 18:24
 */


/**
 * 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，
 * 每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，
 * 输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 * <p>
 * 思路：
 * (1)
 * 暴力遍历对比
 * (2)
 * 将矩阵看成一个坐标轴
 * 从右上角开始比对，如果大于 则target向下移动，小于则向左
 */
public class Test02_二维数组中的查找 {


    public boolean test(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int a = matrix.length;
        int b = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int y = 0; y < matrix[i].length; y++) {
                if (matrix[i][y] == target) {
                    return true;
                }
            }
        }
        return false;

    }

    public boolean test1(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int a = 0;
        int b = matrix[0].length - 1;
        while (a < matrix.length && b >= 0) {
            if (target == matrix[a][b]) {
                return true;
            } else if (target < matrix[a][b]) {
                b--;
            } else {
                a++;
            }

        }
        return false;


    }

    /**
     * {{1, 4, 7, 11, 15}
     * {2, 5, 8, 12, 19}
     * {3, 6, 9, 16, 22}
     * {10, 13, 14, 17, 24},
     * {18, 21, 23, 26, 30}}
     */


}
